1. Techinal Field
The invention relates to databases. More particularly, the invention relates to a depth-first join for a database.
2. Description of the Prior Art
In databases, a join is a type of query that combines data from multiple tables. Inner joins are a subclass of joins that project the results of a set of restrictions applied to the Cartesian product of all rows in the participating tables. Existing commercial databases execute joins in a breadth-first manner. Typically, a query optimizer examines the request and applies heuristics to generate a query execution plan which describes, among other things, the order in which the tables are to be combined (joined) to obtain the result set. Tables are joined in a pairwise manner. The result of the combination of two tables is itself a table. In general, the combination of N tables requires N−1 join steps. At each step, the candidate rows are extracted from both tables and combined.
A disadvantage of the breadth-first join is that the storage requirements for the intermediate tables grow with database size. It is conceivable that the temporary storage required for a join in a large, distributed database could overwhelm the resources of a single machine. To ensure adequate performance on very large data sets, it would be desirable to employ a technique for performing a join using a constant-space mechanism with an asymptotic time complexity that is no worse than a traditional breadth-first join.